
// 72.编辑距离
class Solution {
public:
    int minDistance(string word1, string word2) {
        // 就是在word1中找word2的最长子序列
        int n = word1.size() , m = word2.size();
        if(n == 0) return m;
        if(m == 0) return n;
        word1 = " " + word1 , word2 = " " + word2;
        // 用动态规划来解决
        const int INF = 0x3f3f3f3f;
        vector<vector<int>> dp(n + 1 , vector<int>(m + 1));
        for(int i = 0 ; i <= n ; i++) dp[i][0] = i;
        for(int i = 0 ; i <= m ; i++) dp[0][i] = i;

        for(int i = 1 ; i <= n ;i++)
            for(int j = 1 ; j <= m ; j++)
                if(word2[j] == word1[i]) dp[i][j] = dp[i - 1][j - 1] ;
                else 
                    dp[i][j] = min({dp[i - 1][j - 1] , dp[i - 1][j] , dp[i][j - 1]}) + 1;

        return dp[n][m];
    }
};